{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Queens That Can Attack the King"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #matrix #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #矩阵 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: queensAttacktheKing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #可以攻击国王的皇后"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在一个&nbsp;<strong>8x8</strong>&nbsp;的棋盘上，放置着若干「黑皇后」和一个「白国王」。</p>\n",
    "\n",
    "<p>给定一个由整数坐标组成的数组&nbsp;<code>queens</code>&nbsp;，表示黑皇后的位置；以及一对坐标&nbsp;<code>king</code> ，表示白国王的位置，返回所有可以攻击国王的皇后的坐标(任意顺序)。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/10/13/untitled-diagram.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>queens = [[0,1],[1,0],[4,0],[0,4],[3,3],[2,4]], king = [0,0]\n",
    "<strong>输出：</strong>[[0,1],[1,0],[3,3]]\n",
    "<strong>解释：</strong> \n",
    "[0,1] 的皇后可以攻击到国王，因为他们在同一行上。 \n",
    "[1,0] 的皇后可以攻击到国王，因为他们在同一列上。 \n",
    "[3,3] 的皇后可以攻击到国王，因为他们在同一条对角线上。 \n",
    "[0,4] 的皇后无法攻击到国王，因为她被位于 [0,1] 的皇后挡住了。 \n",
    "[4,0] 的皇后无法攻击到国王，因为她被位于 [1,0] 的皇后挡住了。 \n",
    "[2,4] 的皇后无法攻击到国王，因为她和国王不在同一行/列/对角线上。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/10/13/untitled-diagram-1.jpg\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>queens = [[0,0],[1,1],[2,2],[3,4],[3,5],[4,4],[4,5]], king = [3,3]\n",
    "<strong>输出：</strong>[[2,2],[3,4],[4,4]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/10/13/untitled-diagram-2.jpg\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>queens = [[5,6],[7,7],[2,1],[0,7],[1,6],[5,1],[3,7],[0,3],[4,0],[1,2],[6,3],[5,0],[0,4],[2,2],[1,1],[6,4],[5,4],[0,0],[2,6],[4,5],[5,2],[1,4],[7,5],[2,3],[0,5],[4,2],[1,0],[2,7],[0,1],[4,6],[6,1],[0,6],[4,3],[1,7]], king = [3,4]\n",
    "<strong>输出：</strong>[[2,3],[1,4],[1,6],[3,7],[4,3],[5,4],[4,5]]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= queens.length&nbsp;&lt;= 63</code></li>\n",
    "\t<li><code>queens[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= queens[i][j] &lt;&nbsp;8</code></li>\n",
    "\t<li><code>king.length == 2</code></li>\n",
    "\t<li><code>0 &lt;= king[0], king[1] &lt; 8</code></li>\n",
    "\t<li>一个棋盘格上最多只能放置一枚棋子。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [queens-that-can-attack-the-king](https://leetcode.cn/problems/queens-that-can-attack-the-king/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [queens-that-can-attack-the-king](https://leetcode.cn/problems/queens-that-can-attack-the-king/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,1],[1,0],[4,0],[0,4],[3,3],[2,4]]\\n[0,0]', '[[0,0],[1,1],[2,2],[3,4],[3,5],[4,4],[4,5]]\\n[3,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import Queue\n",
    "\n",
    "STEPS = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (-1, -1), (1, -1), (-1, 1)]\n",
    "\n",
    "class Solution:\n",
    "    def queensAttacktheKing(self, queens: List[List[int]], king: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        queens = set(map(tuple, queens))\n",
    "        q = Queue()\n",
    "        for step in STEPS:\n",
    "            cur = (king[0] + step[0], king[1] + step[1])\n",
    "            if cur in queens:\n",
    "                res.append(cur)\n",
    "            else:\n",
    "                q.put((cur[0], cur[1], step[0], step[1]))\n",
    "                \n",
    "        while not q.empty():\n",
    "            cur = q.get()\n",
    "            child = (cur[0] + cur[2], cur[1] + cur[3])\n",
    "            if child[0] < 0 or child[0] >= 8 or child[1] < 0 or child[1] >= 8:\n",
    "                continue\n",
    "            if child in queens:\n",
    "                res.append(child)\n",
    "                continue\n",
    "            q.put(child + (cur[2], cur[3]))\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queensAttacktheKing(self, queens: List[List[int]], king: List[int]) -> List[List[int]]:\n",
    "        pan = [[0 for i in range(8)] for j in range(8)]\n",
    "        res = []\n",
    "        for q in queens:\n",
    "            pan[q[0]][q[1]] = 1\n",
    "        print(pan)\n",
    "        kx = king[0]\n",
    "        ky = king[1]\n",
    "        x = kx\n",
    "        y = ky\n",
    "        while x >= 0 and x < 8:\n",
    "            if pan[x][y] == 1:\n",
    "                res.append([x,y])\n",
    "                break\n",
    "            else:\n",
    "                x -= 1\n",
    "        x = kx\n",
    "        y = ky\n",
    "        while x >= 0 and x < 8:\n",
    "            if pan[x][y] == 1:\n",
    "                res.append([x,y])\n",
    "                break\n",
    "            else:\n",
    "                x += 1\n",
    "        x = kx\n",
    "        y = ky\n",
    "        while y >= 0 and y < 8:\n",
    "            if pan[x][y] == 1:\n",
    "                res.append([x,y])\n",
    "                break\n",
    "            else:\n",
    "                y -= 1\n",
    "        x = kx\n",
    "        y = ky\n",
    "        while y >= 0 and y < 8:\n",
    "            if pan[x][y] == 1:\n",
    "                res.append([x,y])\n",
    "                break\n",
    "            else:\n",
    "                y += 1\n",
    "        x = kx\n",
    "        y = ky\n",
    "        while x >= 0 and x < 8 and y >= 0 and y < 8:\n",
    "            if pan[x][y] == 1:\n",
    "                res.append([x,y])\n",
    "                break\n",
    "            else:\n",
    "                x -= 1\n",
    "                y -= 1\n",
    "        x = kx\n",
    "        y = ky\n",
    "        while x >= 0 and x < 8 and y >= 0 and y < 8:\n",
    "            if pan[x][y] == 1:\n",
    "                res.append([x,y])\n",
    "                break\n",
    "            else:\n",
    "                x -= 1\n",
    "                y += 1\n",
    "        x = kx\n",
    "        y = ky\n",
    "        while x >= 0 and x < 8 and y >= 0 and y < 8:\n",
    "            if pan[x][y] == 1:\n",
    "                res.append([x,y])\n",
    "                break\n",
    "            else:\n",
    "                x += 1\n",
    "                y -= 1\n",
    "        x = kx\n",
    "        y = ky\n",
    "        while x >= 0 and x < 8 and y >= 0 and y < 8:\n",
    "            if pan[x][y] == 1:\n",
    "                res.append([x,y])\n",
    "                break\n",
    "            else:\n",
    "                x += 1\n",
    "                y += 1\n",
    "        return res\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queensAttacktheKing(self, queens: List[List[int]], king: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        row = [king]\n",
    "        col = [king]\n",
    "        dui = [king]\n",
    "        xie = [king]\n",
    "        for x in range(0, len(queens)):\n",
    "            if queens[x][0] == king[0]:\n",
    "                row.append(queens[x])\n",
    "            elif queens[x][1] == king[1]:\n",
    "                col.append(queens[x])\n",
    "            elif queens[x][0] - king[0] == queens[x][1] - king[1]:\n",
    "                dui.append(queens[x])\n",
    "            elif queens[x][0] - king[0] == king[1] - queens[x][1]:\n",
    "                xie.append(queens[x])    \n",
    "        row.sort(key=lambda n: n[1])\n",
    "        col.sort(key=lambda n: n[0])\n",
    "        dui.sort(key=lambda n: n[0])\n",
    "        xie.sort(key=lambda n: n[1])\n",
    "        if len(row)>1:\n",
    "            r = row.index(king)\n",
    "            if r == 0:\n",
    "                res.append(row[1])\n",
    "            elif r == len(row)-1:\n",
    "                res.append(row[r-1])\n",
    "            else:\n",
    "                res.append(row[r-1])\n",
    "                res.append(row[r+1])\n",
    "        if len(col)>1:\n",
    "            c = col.index(king)\n",
    "            if c == 0:\n",
    "                res.append(col[1])\n",
    "            elif c == len(col) - 1:\n",
    "                res.append(col[c-1])\n",
    "            else:\n",
    "                res.append(col[c - 1])\n",
    "                res.append(col[c + 1])\n",
    "        if len(dui)>1:\n",
    "            d = dui.index(king)\n",
    "            if d == 0:\n",
    "                res.append(dui[1])\n",
    "            elif d == len(dui)-1:\n",
    "                res.append(dui[d-1])\n",
    "            else:\n",
    "                res.append(dui[d-1])\n",
    "                res.append(dui[d+1])\n",
    "        if len(xie)>1:\n",
    "            h = xie.index(king)\n",
    "            if h == 0:\n",
    "                res.append(xie[1])\n",
    "            elif h == len(xie)-1:\n",
    "                res.append(xie[h-1])\n",
    "            else:\n",
    "                res.append(xie[h-1])\n",
    "                res.append(xie[h+1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queensAttacktheKing(self, queens: List[List[int]], king: List[int]) -> List[List[int]]:\n",
    "        board = [[False] * 8 for _ in range(8)]\n",
    "        dirs = ((1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1))\n",
    "        for i, j in queens:\n",
    "            board[i][j] = True\n",
    "        res = []\n",
    "        for di, dj in dirs:\n",
    "            i, j = king[0] + di, king[1] + dj\n",
    "            while i >= 0 and i < 8 and j >= 0 and j < 8:\n",
    "                if board[i][j]:\n",
    "                    res.append((i, j))\n",
    "                    break\n",
    "                i += di\n",
    "                j += dj\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queensAttacktheKing(self, queens: List[List[int]], king: List[int]) -> List[List[int]]:\n",
    "        ans=[]\n",
    "        n=8\n",
    "        if not queens:return ans\n",
    "        queens=set([tuple(v) for v in queens])\n",
    "\n",
    "        ki,kj=king[0],king[1]\n",
    "        \n",
    "        for i in range(ki-1,-1,-1):\n",
    "            if (i,kj) in queens:\n",
    "                ans.append((i,kj))\n",
    "                break\n",
    "        \n",
    "        for i in range(ki+1,n):\n",
    "            if (i,kj) in queens:\n",
    "                ans.append((i,kj))\n",
    "                break\n",
    "        \n",
    "        for j in range(kj-1,-1,-1):\n",
    "            if (ki,j) in queens:\n",
    "                ans.append((ki,j))\n",
    "                break\n",
    "        \n",
    "        for j in range(kj+1,n):\n",
    "            if (ki,j) in queens:\n",
    "                ans.append((ki,j))\n",
    "                break\n",
    "\n",
    "        d=min(ki,kj)\n",
    "        for i in range(1,d+1):\n",
    "            if (ki-i,kj-i) in queens:\n",
    "                ans.append((ki-i,kj-i))\n",
    "                break\n",
    "\n",
    "        d=min(n-ki-1,n-kj-1)\n",
    "        for i in range(1,d+1):\n",
    "            if (ki+i,kj+i) in queens:\n",
    "                ans.append((ki+i,kj+i))\n",
    "                break\n",
    "        d=min(ki,n-kj-1)\n",
    "        for i in range(1,d+1):\n",
    "            if (ki-i,kj+i) in queens:\n",
    "                ans.append((ki-i,kj+i))\n",
    "                break\n",
    "        d=min(n-ki-1,kj)\n",
    "        for i in range(1,d+1):\n",
    "            if (ki+i,kj-i) in queens:\n",
    "                ans.append((ki+i,kj-i))\n",
    "                break\n",
    "        \n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queensAttacktheKing(self, queens: List[List[int]], king: List[int]) -> List[List[int]]:\n",
    "        # one by one\n",
    "        r,c = king\n",
    "        kr, kc =[],[]\n",
    "        k1, k2 = [],[]\n",
    "        for q in queens:\n",
    "            x,y=q\n",
    "            if x == r:\n",
    "                kr.append(q)\n",
    "            if y==c:\n",
    "                kc.append(q)\n",
    "            if x-r==y-c:\n",
    "                k1.append(q)\n",
    "            if x-r==c-y:\n",
    "                k2.append(q)\n",
    "        re=[]\n",
    "        kr.sort(key=lambda x:x[1])\n",
    "        for i in range(len(kr)):\n",
    "            if kr[i][1] < c:\n",
    "                if i == len(kr)-1:\n",
    "                    re.append(kr[i])\n",
    "                else:\n",
    "                    if kr[i+1][1]>c:\n",
    "                        re.append(kr[i])\n",
    "                        re.append(kr[i+1])\n",
    "                        break\n",
    "            else:\n",
    "                if i==0 or kr[i-1][1]<c:\n",
    "                    re.append(kr[i])\n",
    "\n",
    "        kc.sort(key=lambda x:x[0])\n",
    "        for i in range(len(kc)):\n",
    "            if kc[i][0] < r:\n",
    "                if i == len(kc)-1:\n",
    "                    re.append(kc[i])\n",
    "                else:\n",
    "                    if kc[i+1][0]>r:\n",
    "                        re.append(kc[i])\n",
    "                        re.append(kc[i+1])\n",
    "                        break\n",
    "            else:\n",
    "                if i == 0 or kc[i - 1][0] < r:\n",
    "                    re.append(kc[i])\n",
    "\n",
    "        kc=k1\n",
    "        kc.sort(key=lambda x: x[0])\n",
    "        for i in range(len(kc)):\n",
    "            if kc[i][0] < r:\n",
    "                if i == len(kc) - 1:\n",
    "                    re.append(kc[i])\n",
    "                else:\n",
    "                    if kc[i + 1][0] > r:\n",
    "                        re.append(kc[i])\n",
    "                        re.append(kc[i + 1])\n",
    "                        break\n",
    "            else:\n",
    "                if i == 0 or kc[i - 1][0] < r:\n",
    "                    re.append(kc[i])\n",
    "        kc=k2\n",
    "        kc.sort(key=lambda x: x[0])\n",
    "        for i in range(len(kc)):\n",
    "            if kc[i][0] < r:\n",
    "                if i == len(kc) - 1:\n",
    "                    re.append(kc[i])\n",
    "                else:\n",
    "                    if kc[i + 1][0] > r:\n",
    "                        re.append(kc[i])\n",
    "                        re.append(kc[i + 1])\n",
    "                        break\n",
    "            else:\n",
    "                if i == 0 or kc[i - 1][0] < r:\n",
    "                    re.append(kc[i])\n",
    "\n",
    "        return re\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queensAttacktheKing(self, queens: List[List[int]], king: List[int]) -> List[List[int]]:\n",
    "        board = [[0]*8 for i in range(8)]\n",
    "        res = []\n",
    "        for x,y in queens:\n",
    "            board[x][y] = 1\n",
    "        def dfs(i,j,dir_i,dir_j):\n",
    "            if not 0<= i < 8 or not 0 <= j < 8:\n",
    "                return\n",
    "            if board[i][j] == 1:\n",
    "                res.append([i,j])\n",
    "                return\n",
    "            dfs(i+dir_i,j+dir_j,dir_i,dir_j)\n",
    "\n",
    "        for i in range(-1,2,1):\n",
    "            for j in range(-1,2,1):\n",
    "                if i or j:\n",
    "                    dfs(king[0],king[1],i,j)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queensAttacktheKing(self, queens: List[List[int]], king: List[int]) -> List[List[int]]:\n",
    "        \n",
    "        nums=[[0 for _ in range(8)] for _ in range(8)]\n",
    "\n",
    "\n",
    "        max_row=king[0]\n",
    "        max_col=king[1]\n",
    "\n",
    "        for ele in queens:\n",
    "            nums[ele[0]][ele[1]]=1\n",
    "            max_row=max(ele[0],max_row)\n",
    "            max_col=max(ele[1],max_col)\n",
    "        # print(nums,max_row,max_col)\n",
    "        ans=[]\n",
    "        \n",
    "        direction=[[-1,-1],[0,1],[1,0],[-1,0],[0,-1],[1,-1],[1,1],[-1,1]]\n",
    "\n",
    "        for de in direction:\n",
    "            temp=king.copy()\n",
    "            # print(temp)\n",
    "            while(0<=temp[0]<=max_row and 0<=temp[1]<=max_col):\n",
    "                if nums[temp[0]][temp[1]]==1:\n",
    "                    ans.append([temp[0],temp[1]])\n",
    "                    break\n",
    "                else:\n",
    "                    temp[0]+=de[0]\n",
    "                    temp[1]+=de[1]\n",
    "                # print(temp)\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queensAttacktheKing(self, queens: List[List[int]], king: List[int]) -> List[List[int]]:\n",
    "        p = {(x, y) for x, y in queens}\n",
    "        d = {(1, 0), (0, 1), (0, -1), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)}\n",
    "        kx, ky = king\n",
    "        ans = []\n",
    "        for t in range(1, 8):\n",
    "            c = set()\n",
    "            for i, j in d:\n",
    "                q = (kx + t * i, ky + t * j)\n",
    "                if q in p:\n",
    "                    ans += [q]\n",
    "                    c |= {(i, j)}\n",
    "            d -= c\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queensAttacktheKing(self, queens: List[List[int]], king: List[int]) -> List[List[int]]:\n",
    "        p = {(x, y) for x, y in queens}\n",
    "        d = {(1, 0), (0, 1), (0, -1), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)}\n",
    "        kx, ky = king\n",
    "        ans = []\n",
    "        for t in range(1, 8):\n",
    "            c = set()\n",
    "            for i, j in d:\n",
    "                q = (kx + t * i, ky + t * j)\n",
    "                if q in p:\n",
    "                    ans += [q]\n",
    "                    c |= {(i, j)}\n",
    "            d -= c\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queensAttacktheKing(self, queens: List[List[int]], king: List[int]) -> List[List[int]]:\n",
    "        ki = king[0]\n",
    "        kj = king[1]\n",
    "        queen = [[ki,kj] for _ in range(8)]\n",
    "        #print(queen)\n",
    "        for i,j in queens:\n",
    "            mj = j - kj\n",
    "            mi = i - ki\n",
    "            print(mi,mj)\n",
    "            if mi == 0 and j > kj:\n",
    "                if queen[0][1] == kj:\n",
    "                    queen[0][1] = j\n",
    "                else:\n",
    "                    queen[0][1] = min(queen[0][1],j)\n",
    "            elif mi == 0 and j < kj:\n",
    "                if queen[1][1] == kj:\n",
    "                    queen[1][1] = j\n",
    "                else:\n",
    "                    queen[1][1] = max(queen[1][1],j)\n",
    "            elif mj == 0 and i < ki:\n",
    "                if queen[2][0] == ki:\n",
    "                    queen[2][0] = i\n",
    "                else:\n",
    "                    queen[2][0] = max(queen[2][0],i)\n",
    "            elif mj == 0 and i > ki:\n",
    "                if queen[3][0] == ki:\n",
    "                    queen[3][0] = i\n",
    "                else:\n",
    "                    queen[3][0] = min(queen[3][0],i)\n",
    "            elif mj == mi and mi > 0:\n",
    "                if queen[4][0] == ki and queen[4][1] == kj:\n",
    "                    queen[4][0] = i\n",
    "                    queen[4][1] = j\n",
    "                else:\n",
    "                    queen[4][0] = min(queen[4][0],i)\n",
    "                    queen[4][1] = min(queen[4][1],j)\n",
    "            elif mj == mi and mi < 0:\n",
    "                if queen[5][0] == ki and queen[5][1] == kj:\n",
    "                    queen[5][0] = i\n",
    "                    queen[5][1] = j\n",
    "                else:\n",
    "                    queen[5][0] = max(queen[5][0],i)\n",
    "                    queen[5][1] = max(queen[5][1],j)\n",
    "            elif mj == -mi and mi > 0:\n",
    "                if queen[6][0] == ki and queen[6][1] == kj:\n",
    "                    queen[6][0] = i\n",
    "                    queen[6][1] = j\n",
    "                else:\n",
    "                    queen[6][0] = min(queen[6][0],i)\n",
    "                    queen[6][1] = max(queen[6][1],j)\n",
    "            elif mj == -mi and mi < 0:\n",
    "                if queen[7][0] == ki and queen[7][1] == kj:\n",
    "                    queen[7][0] = i\n",
    "                    queen[7][1] = j\n",
    "                else:\n",
    "                    queen[7][0] = max(queen[7][0],i)\n",
    "                    queen[7][1] = min(queen[7][1],j)\n",
    "        #print(queen)\n",
    "        res = []\n",
    "        for q in queen:\n",
    "            if q != king:\n",
    "                res.append(q)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queensAttacktheKing(self, queens: List[List[int]], king: List[int]) -> List[List[int]]:\n",
    "        a = [[0 for _ in range(8)] for _ in range(8)]\n",
    "        for r,c in queens:                  #状态标记  queen所在的位置 置1\n",
    "            a[r][c] = 1\n",
    "        \n",
    "        res = []\n",
    "        dirs = [[-1,-1],[-1,0],[-1,1],[0,1],[1,1],[1,0],[1,-1],[0,-1]]  #8个方向\n",
    "        for dr,dc in dirs:                  #遍历 每次照着一个方向一路查找\n",
    "            r,c = king[0], king[1]\n",
    "            nr, nc = r + dr, c + dc\n",
    "            while 0<=nr<8 and 0<=nc<8:      #只要还没出边界\n",
    "                if a[nr][nc] == 1:\n",
    "                    res.append([nr, nc])\n",
    "                    break\n",
    "                nr = nr + dr                    #按照这个方向一直找  直到找到或者和出了范围\n",
    "                nc = nc + dc\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queensAttacktheKing(self, queens: List[List[int]], king: List[int]) -> List[List[int]]:\n",
    "        a=[[0 for i in range(8)] for _ in range(8)]\n",
    "        for r,c in queens:\n",
    "            a[r][c]=1\n",
    "        ans=[]\n",
    "        dirs=[[0,1],[1,1],[1,0],[1,-1],[0,-1],[-1,-1],[-1,0],[-1,1]]\n",
    "        for dr,dc in dirs:\n",
    "            kr,kc=king[0],king[1]\n",
    "            kr+=dr\n",
    "            kc+=dc\n",
    "            while 0<=kr<8 and 0<=kc<8:\n",
    "                if a[kr][kc]==1:\n",
    "                    ans.append([kr,kc])\n",
    "                    break\n",
    "                kr+=dr\n",
    "                kc+=dc\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queensAttacktheKing(self, queens: List[List[int]], king: List[int]) -> List[List[int]]:\n",
    "        m, n = 8, 8\n",
    "        qs = set()\n",
    "        for x, y in queens:\n",
    "            qs.add((x, y))\n",
    "        vis = set()\n",
    "        ans = []\n",
    "        tx, ty = 0, 0\n",
    "        def dfs(x, y, d):\n",
    "            nonlocal ans, tx, ty\n",
    "            if (x, y) == (king[0], king[1]):\n",
    "                ans.append([tx, ty])\n",
    "                return\n",
    "            dx, dy = d\n",
    "            nx, ny = x + dx, y + dy\n",
    "            if 0 <= nx < m and 0 <= ny < n and (nx, ny) not in vis and (nx, ny) not in qs:\n",
    "                vis.add((nx, ny))\n",
    "                dfs(nx, ny, d)\n",
    "                    \n",
    "        for x, y in queens:\n",
    "            vis = set()\n",
    "            tx, ty = x, y\n",
    "            vis.add((x, y))\n",
    "            for d in [(0, 1), (1, 0), (0, -1), (-1, 0)] + [(1, 1), (-1, -1), (1, -1), (-1, 1)]:\n",
    "                dfs(x, y, d)\n",
    "            \n",
    "        return ans\n",
    "    # 输出：[[2,3],[1,4],[1,6],[3,7],[4,3],[5,4],[4,5]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queensAttacktheKing(self, queens: List[List[int]], king: List[int]) -> List[List[int]]:\n",
    "        t = [[0 for i in range(8)] for i in range(8)]\n",
    "        for q in queens:\n",
    "            t[q[0]][q[1]] = 1\n",
    "        ans = []  \n",
    "        i,j = king[0],king[1]\n",
    "        # n = 8\n",
    "        while(i>0 and j>0):\n",
    "            i-=1\n",
    "            j-=1\n",
    "            if(t[i][j]==1):\n",
    "                ans.append([i,j])\n",
    "                break\n",
    "        i,j = king[0],king[1]\n",
    "        while(i>0 and j<7):\n",
    "            i-=1\n",
    "            j+=1\n",
    "            if(t[i][j]==1):\n",
    "                ans.append([i,j])\n",
    "                break\n",
    "        i,j = king[0],king[1]\n",
    "        while(i<7 and j>0):\n",
    "            i+=1\n",
    "            j-=1\n",
    "            if(t[i][j]==1):\n",
    "                ans.append([i,j])\n",
    "                break\n",
    "        i,j = king[0],king[1]\n",
    "        while(i<7 and j<7):\n",
    "            i+=1\n",
    "            j+=1\n",
    "            if(t[i][j]==1):\n",
    "                ans.append([i,j])\n",
    "                break\n",
    "        i,j = king[0],king[1]\n",
    "        while(i>0):\n",
    "            i-=1\n",
    "            if(t[i][j]==1):\n",
    "                ans.append([i,j])\n",
    "                break\n",
    "        i,j = king[0],king[1]\n",
    "        while(j>0):\n",
    "            j-=1\n",
    "            if(t[i][j]==1):\n",
    "                ans.append([i,j])\n",
    "                break\n",
    "        i,j = king[0],king[1]\n",
    "        while(i<7):\n",
    "            i+=1\n",
    "            if(t[i][j]==1):\n",
    "                ans.append([i,j])\n",
    "                break    \n",
    "        i,j = king[0],king[1]\n",
    "        while(j<7):\n",
    "            j+=1\n",
    "            if(t[i][j]==1):\n",
    "                ans.append([i,j])\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queensAttacktheKing(self, queens: List[List[int]], king: List[int]) -> List[List[int]]:\n",
    "        def dfs(i, j, n, m):\n",
    "            print(i, j, n, m)\n",
    "            if not (0 <= n < 8 and 0 <= m < 8) :\n",
    "                return\n",
    "            if [n, m] in queens:\n",
    "                ll.append([n, m])\n",
    "                return\n",
    "            dfs(i, j, n+i, m+j)\n",
    "\n",
    "\n",
    "\n",
    "        dirs = [(1, 0),(-1, 0), (0, 1), (0, -1), (1, 1), (-1, -1),(1, -1),(-1, 1)]\n",
    "        ll = []\n",
    "        for i, j in dirs:\n",
    "            n, m = king\n",
    "            dfs(i, j, n, m)           \n",
    "            # while 0 <= n < 8 and 0 <= m < 8 :\n",
    "            #     print(n, m)    \n",
    "            #     if [n, m] in queens:\n",
    "            #         ll.append([n, m])\n",
    "            #         break\n",
    "            #     n += i\n",
    "            #     m += j\n",
    "        return ll     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queensAttacktheKing(self, queens: List[List[int]], king: List[int]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        move = [(0, 1), (0, -1), (-1, 0), (1, 0), (-1, -1), (-1, 1), (1, -1), (1, 1)]\n",
    "        for m in move:\n",
    "            cur = king\n",
    "            while cur[0] >= 0 and cur[0] < 8 and cur[1] >= 0 and cur[1] < 8:\n",
    "                cur = [cur[0] + m[0], cur[1] + m[1]]\n",
    "                if cur in queens:\n",
    "                    ans.append(cur)\n",
    "                    break\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queensAttacktheKing(self, queens: List[List[int]], king: List[int]) -> List[List[int]]:\n",
    "        queen_pos = set((x, y) for x, y in queens)\n",
    "        ans = list()\n",
    "        for dx in [-1, 0, 1]:\n",
    "            for dy in [-1, 0, 1]:\n",
    "                if dx == dy == 0:\n",
    "                    continue\n",
    "                \n",
    "                kx, ky = king[0] + dx, king[1] + dy\n",
    "                while 0 <= kx < 8 and 0 <= ky < 8:\n",
    "                    if (kx, ky) in queen_pos:\n",
    "                        ans.append([kx, ky])\n",
    "                        break\n",
    "                    kx += dx\n",
    "                    ky += dy\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def queensAttacktheKing(self, queens: List[List[int]], king: List[int]) -> List[List[int]]:\n",
    "        def search(queens, x, y, direction):\n",
    "            if x < 0 or y < 0 or x >= 8 or y >= 8:\n",
    "                return None\n",
    "            if (x, y) in queens:\n",
    "                return [x, y]\n",
    "            return search(queens, x + direction[0], y + direction[1], direction)\n",
    "        \n",
    "        res = []\n",
    "        queens = set([(x, y) for x, y in queens])\n",
    "        for x in [-1, 0, 1]:\n",
    "            for y in [-1, 0, 1]:\n",
    "                if x == 0 and y == 0:\n",
    "                    continue\n",
    "                q = search(queens, king[0] + x, king[1] + y, [x, y])\n",
    "                # print([x, y], q)\n",
    "                if q:\n",
    "                    res.append(q)\n",
    "        return res\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
